package leetCode;

import java.util.Arrays;
import java.util.Scanner;

/*

8
10 9 2 5 3 7 101 18
 1 1 1 2 2 3   4  4

6
4 10 4 3 8 9
1  2 1 1 2 3

6
0 1 0 3 2 3
1 2 1 3 3 4

9
1 3 6 7 9 4 10 5 6
1 2 3 4 5 3  6 4 5

 */

public class Solution300 {
    
    public int lengthOfLIS(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n];
        // 初始化dp数组
        for (int i = 0; i < n; i++) {
            dp[i] = 1;
        }
        
        int max = 1;
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            if (dp[i] > max) {
                max = dp[i];
            }
        }
        System.out.println(Arrays.toString(dp));
        return max;
    }

    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int[] nums = new int[n];
        for (int i = 0; i < n; i++) {
            nums[i] = scan.nextInt();
        }
        Solution300 s = new Solution300();
        System.out.println(s.lengthOfLIS(nums));

    }

}
